//
// Created by ASUS on 2024/3/20.
//
#include <bits/stdc++.h>
using namespace std;

//前缀和不能为负数
int countSubarrays(vector<int>& nums, int k) {
	int n = nums.size();
	vector<long long> s(n);
	partial_sum(nums.begin(), nums.end(), s.begin());
	vector<int> f(n,0);
	unordered_map<int, int> cnt;
	for(int i=0; i<n; i++) {
		f[i]+=(s[i]%k==0);
		f[i]+=cnt[s[i]%k];
		cnt[s[i]%k]++;
	}
	return accumulate(f.begin(), f.end(), 0LL);
}

//前缀和可以为负数
int countSubarrays1(vector<int>& nums, int k) {
	int n = nums.size();
	vector<long long> s(n);
	partial_sum(nums.begin(), nums.end(), s.begin());
	vector<int> f(n,0);
	unordered_map<int, int> cnt;
	for(int i=0; i<n; i++) {
		f[i]+=((s[i]%k+k)%k==0);
		f[i]+=cnt[(s[i]%k+k)%k];
		cnt[(s[i]%k+k)%k]++;
	}
	return accumulate(f.begin(), f.end(), 0LL);
}